package cn.edu.scut.hsrc.cluster.semantic;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import cn.edu.scut.hsrc.bean.CandidatePhrase;
import cn.edu.scut.hsrc.bean.CandidateWord;
import cn.edu.scut.hsrc.bean.Doc;
import cn.edu.scut.hsrc.bean.Pair;
import cn.edu.scut.hsrc.bean.PhraseSegment;
import cn.edu.scut.hsrc.bean.PhraseSegment.TitleFlag;
import cn.edu.scut.hsrc.bean.RefWord;
import cn.edu.scut.hsrc.bean.SeqDoc;
import cn.edu.scut.hsrc.bean.SeqSegment;
import cn.edu.scut.hsrc.bean.SeqWord;
import cn.edu.scut.hsrc.bean.Word;
import cn.edu.scut.hsrc.bean.Word.RelationToQuery;
import cn.edu.scut.hsrc.bean.WordSet;
import cn.edu.scut.hsrc.bean.WordType.Type;
import cn.edu.scut.hsrc.output.ClusterResult;
import cn.edu.scut.hsrc.output.Label;
import cn.edu.scut.hsrc.trie.TrieTree;
import cn.edu.scut.hsrc.util.Configuration;

/**
 * 实现聚类的类
 * <br>主要功能：
 * <br>1、以中心词扩展候选短语，并计算该短语的独立性得分，选取得分最高的短语作为该候选词扩展的候选短语；
 * <br>2、根据独立性得分，对计算完的候选短语进行排序；
 * <br>3、选取得分较高的候选短语，根据这些短语对文档进行聚类 ；
 * <br>4、返回聚类结果。
 * @file Cluster.java
 * @author feiyu
 *
 */

public class Cluster {
	
	private static final Configuration configure = Configuration.getInstance();
	
	private static double INDEPENDENCE_THRESHOLD;			//短语左右独立性的最低阈值
	private static double PHRASE_DOC_RELATION_THRESHOLD;	//短语和文档关系得分的阈值
	private static int CLUSTER_NUM;							//最后聚类结果的数目
	
	private static final double INVALID_SCORE = -10000;
	
	static{
		INDEPENDENCE_THRESHOLD = configure.getDouble("hsrc.lr.independent.threshold", 2);
		PHRASE_DOC_RELATION_THRESHOLD = configure.getDouble("hsrc.phrase.doc.relation.threshold", 0.3);
		CLUSTER_NUM = configure.getInt("hsrc.cluster.count", 10);
	}
	

	private final Doc [] docs;									//文档
	private final SeqDoc [] seqDocs;							//文档的有序词描述集合
	private final WordSet [] docWords;							//文档包含词的集合（只包查询词、含动、名词）
	private final WordSet allWords;								//所有文档出现的词（只包查询词、含动、名词）
	private Pair<Double, Double> [] leftRightScores;			//对应allWords中的词的左右独立性得分
	private final List<CandidateWord> candidateWords;			//候选词列表
	private final int [][] docSimMatrix;						//文档相似度矩阵
	
	
	
	/**
	 * 
	 * 构造函数
	 * @param docs				文档
	 * @param seqDocs			文档的有序词描述集合
	 * @param docWords			文档包含词的集合
	 * @param allWords			所有文档出现的词
	 * @param candidateWords	候选词列表
	 * @param docSimMatrix		文档相似度矩阵
	 */
	@SuppressWarnings("unchecked")
	public Cluster(Doc [] docs,SeqDoc[] seqDocs,WordSet[] docWords,WordSet allWords,List<CandidateWord> candidateWords,int [][] docSimMatrix) {
		// TODO Auto-generated constructor stub
		this.docs = docs;
		this.docWords = docWords;
		this.allWords = allWords;
		this.seqDocs = seqDocs;
		this.candidateWords = candidateWords;
		this.docSimMatrix = docSimMatrix;
		int count = this.allWords.count();
		this.leftRightScores = new Pair[count];
		for(int i=0;i<count;i++)
			this.leftRightScores[i] = new Pair<Double, Double>(INVALID_SCORE,INVALID_SCORE);
	}
	
	/**
	 * 根据前面预处理和关联分析，对所有文档进行聚类，返回聚类结果列表
	 * @return 返回聚类结果列表
	 */
	public ClusterResult[] doCluster()
	{
		//以候选词为中心，产生候选短语，候选短语要求前后两个词必须是动词或者是名词，而且长度要大于或等于2
		//然后计算该短语的左右独立性得分
		List<CandidatePhrase> candidatePhrases = genCandidatePhrases();
		//对候选短语进行标签打分，并排序
		candidatePhrases = scoreLable(candidatePhrases);
		
		for (CandidatePhrase candidatePhrase : candidatePhrases) {
			System.out.println(candidatePhrase.getLabel().getText());
		}
		
		//选取得分高的候选短语，计算它们的标签
		int size = candidatePhrases.size();
		if(size > CLUSTER_NUM)
			size = CLUSTER_NUM;
		//根据候选短语，对原始文档进行聚类，产生聚类结果  
		return cluster(candidatePhrases.subList(0, size));
	}
	
	//add by tyc
	//用于生成候查询推荐短语。
	public List<CandidatePhrase> getCandidateSuggPhrase()
	{
		//以候选词为中心，产生候选短语，候选短语要求前后两个词必须是动词或者是名词，而且长度要大于或等于2
		//然后计算该短语的左右独立性得分
		List<CandidatePhrase> candidatePhrases = genCandidatePhrases();
		//对候选短语进行标签打分，并排序
		candidatePhrases = scoreLable(candidatePhrases);
		return candidatePhrases;
	}
	
	//这个函数的存在只是为了单纯的测试字典树
	public void testTrieTree()
	{
		//以候选词为中心，产生候选短语，候选短语要求前后两个词必须是动词或者是名词，而且长度要大于或等于2
		//然后计算该短语的左右独立性得分
		List<CandidatePhrase> candidatePhrases = genCandidatePhrases();
		//对候选短语进行标签打分，并排序
		candidatePhrases = scoreLable(candidatePhrases);
		int size = candidatePhrases.size();
		TrieTree tree = new TrieTree();
		for(int i=0;i<size;i++)
		{
			CandidatePhrase phrase = candidatePhrases.get(i);

			tree.addDocument(i, phrase.getSeqWords());
		}
		tree.build();
		tree.print(10);
	}
	
	
	/**
	 * 循环遍历所有的候选词，以每个候选词为中心扩展，计算出它的候选短语集，然后对短语进行左右独立性得分计算，
	 * 选取左右独立性得分最高的短语作为以该候选词为中心词的候选短语，加入到候选短语集合中
	 * @return
	 */
	private List<CandidatePhrase> genCandidatePhrases()
	{
		List<CandidatePhrase> candidatePhrases = new ArrayList<CandidatePhrase>();	//保存产生的候选短语
		List<Word> alreadyWords = new ArrayList<Word>();							//保存已经计算完的候选词
		int WORD_NUM = this.candidateWords.size();
		for(int i=0;i<WORD_NUM;i++)
		{
			CandidateWord word = this.candidateWords.get(i);						//获取候选词
			if(word.getRelationToQuery() == RelationToQuery.EQUAL 
					|| word.getRelationToQuery() == RelationToQuery.RINCLUDE)
				continue;
			
			RefWord globalRefWord = this.allWords.getWord(word.getPos());			//获取该候选词在全局词中包含的信息
			List<CandidatePhrase> wordPhrases = new ArrayList<CandidatePhrase>();	//定义保存该候选词扩展的短语
			//计算以该候选词为中心的所有短语的独立性得分，选出最高得分的候选短语
			Map<Integer, List<Integer>> globalRefs = globalRefWord.getRefs();		//获取包含该候选词的<文档,段号>集合
			Iterator<Map.Entry<Integer, List<Integer>>> iterator = globalRefs.entrySet().iterator();
			while (iterator.hasNext()) {
				Map.Entry<Integer, List<Integer>> entry = iterator.next();
				int docIndex = entry.getKey();				//文档编号
				List<Integer> segments = entry.getValue();	//段号
				//计算出该文档所产生的短语
				List<CandidatePhrase> phrases = genCandidatePhrases(docIndex, globalRefWord.getText(), segments, alreadyWords,word);
				for (CandidatePhrase candidatePhrase : phrases) {
					int index = wordPhrases.indexOf(candidatePhrase);
					if(index == -1)
					{
						//如果前面的文档还没有扩展到，那直接加入短语集合
						wordPhrases.add(candidatePhrase);
					}else {
						//如果前面的文档扩展到了，需要判断那个短语包含的词数，保留词少的那个短语，这样保证的短语的简洁性，
						//同时也要加入文档编号
						if(wordPhrases.get(index).count() <= candidatePhrase.count())
						{//如果前面扩展的更简洁
							wordPhrases.get(index).addDoc(docIndex);
							wordPhrases.get(index).addPhraseSegment(candidatePhrase.getPhraseSegment(0));
							wordPhrases.get(index).addTitleFlag(candidatePhrase.getTitleFlag(0));
						}
						else {//如果后面扩展的更简洁
							candidatePhrase.addDocs(wordPhrases.get(index).getDocs());
							List<PhraseSegment> tmpList = wordPhrases.get(index).getPhraseSegments();
							List<TitleFlag> tmpFlags = wordPhrases.get(index).getTitleFlags();
							int size = tmpList.size();
							for (int j=0;j<size;j++) {
								candidatePhrase.addPhraseSegment(tmpList.get(j));
								candidatePhrase.addTitleFlag(tmpFlags.get(j));
							}
							wordPhrases.set(index, candidatePhrase);
						}
					}
				}
			}
			
			//计算短语的独立性得分，选取得分的最高的短语为该查询词扩展得到的短语
			//由同一个候选词扩展的多个独立性得分相同的候选短语，选择那个不被包含的文档数最少的那个短语作为该词的候选短语
			CandidatePhrase maxPhrase = getBestPhrases(word, wordPhrases);
			//加入到候选短语集合中去
			if(maxPhrase != null)//有可能为空，左右独立性得分都低于阈值
				candidatePhrases.add(maxPhrase);
			//把该候选词加入到已经计算完的候选词集合中
			alreadyWords.add(word);
		}
		return candidatePhrases;
	}
	
	/**
	 * 计算出文档docIndex所产生的短语集合
	 * <br>注意这个阶段产生的每个短语保存的段信息是这个文档描述这个短语的最好的分段的信息
	 * @param docIndex
	 * @param centerWord
	 * @param segments
	 * @param alreadyWords
	 * @return
	 */
	private List<CandidatePhrase> genCandidatePhrases(int docIndex,String centerWord,List<Integer> segments,List<Word> alreadyWords,CandidateWord word)
	{
		List<CandidatePhrase> candidatePhrases = new ArrayList<CandidatePhrase>();
		//找到该候选词在文档docIndex中出现的反引用位置
		Map<Integer, List<Integer>> docRefs = this.docWords[docIndex].getWord(centerWord).getRefs();	//<段，段偏移>
		//逐段进行扩展短语，候选短语要求前后两个词必须是动词或者是名词，而且长度要大于或等于2
		int size = segments.size();
		int titleLevel = this.seqDocs[docIndex].getSeparator();
		for(int j=0;j<size;j++)
		{
			List<Integer> offsets = docRefs.get(segments.get(j));	//获取在文档docIndex中第j段中候选词word的出现情况（偏移）
			SeqSegment currSegment = this.seqDocs[docIndex].getSegment(segments.get(j));
			//计算当前分段扩展得分的短语集合
			List<CandidatePhrase> phrases = genCandidatePhrases(currSegment, offsets,alreadyWords,word);
			TitleFlag titleFlag = (segments.get(j)<titleLevel)?TitleFlag.YES:TitleFlag.NO;
			for (CandidatePhrase candidatePhrase : phrases) {
				int index = candidatePhrases.indexOf(candidatePhrase);
				//如果以前的分段没有扩展到该短语
				if(index == -1)
				{
					//如果前面的分段还没有扩展到，加入文档编号
					//这里不需要修改段信息，第0个文档对应第0个段信息
					candidatePhrase.addDoc(docIndex);
					candidatePhrase.addTitleFlag(titleFlag);
					candidatePhrases.add(candidatePhrase);
				}else {
					//如果前面的分段扩展到了，则不需要添加文档编号，那就选择比较词数较少的那个分段
					//比较前后两次扩展的短语哪个更简洁，保留简洁的
					if(candidatePhrases.get(index).count() > candidatePhrase.count())
					{
						candidatePhrase.addDoc(docIndex);
						candidatePhrase.addTitleFlag(titleFlag);
						candidatePhrases.set(index, candidatePhrase);
						//candidatePhrase.setTitleFlag(index, titleFlag);
					}
				}
			}
		}
		return candidatePhrases;
	}
	
	
	/**
	 * 分析段中以候选词为中心的段，计算出候选短语
	 * @param segment	段
	 * @param positions	中心词出现的位置
	 * @param alreadyWords	已经计算完的候选词集合
	 * @return
	 */
	private List<CandidatePhrase> genCandidatePhrases(SeqSegment segment,List<Integer> positions,List<Word> alreadyWords,CandidateWord word)
	{
		
		int size = positions.size();
		if(segment == null || size == 0)
			return new ArrayList<CandidatePhrase>();
		int length = segment.length();
		int start = -1,mid = -1,end = -1;
		if(size == 1)
		{
			start = 0;
			mid = positions.get(0);
			end = length;
			return genCandidatePhrases(segment, start, mid, end, alreadyWords,word);
		}else {
			List<CandidatePhrase> candidatePhrases = new ArrayList<CandidatePhrase>();
			//处理第一个
			candidatePhrases.addAll(genCandidatePhrases(segment, 0, positions.get(0),  positions.get(1), alreadyWords,word));
			//处理中间部分
			for(int i=1;i<size-1;i++)
			{
				List<CandidatePhrase> tmpPhrases = genCandidatePhrases(segment, positions.get(i-1), positions.get(i), positions.get(i+1), alreadyWords,word);
				//把tmpPhrases加入到candidatePhrases，但是需要去重
				for (CandidatePhrase candidatePhrase : tmpPhrases) {
					int index = candidatePhrases.indexOf(candidatePhrase);
					if(index == -1)//如果该分段的其他部分没有扩展到该短语
					{
						candidatePhrases.add(candidatePhrase);
					}else {//如果该分段的其他部分已经扩展了该短语，那就选择比较词数较少的那个部分
						if(candidatePhrases.get(index).count() > candidatePhrase.count())
						{
							candidatePhrases.set(index, candidatePhrase);
						}
					}
				}
			}
			//处理最后一个
			List<CandidatePhrase> tmpPhrases = genCandidatePhrases(segment, positions.get(size-1), positions.get(size-1), length, alreadyWords,word);
			//把tmpPhrases加入到candidatePhrases，但是需要去重
			for (CandidatePhrase candidatePhrase : tmpPhrases) {
				int index = candidatePhrases.indexOf(candidatePhrase);
				if(index == -1)//如果该分段的其他部分没有扩展到该短语
				{
					candidatePhrases.add(candidatePhrase);
				}else {//如果该分段的其他部分已经扩展了该短语，那就选择比较词数较少的那个部分
					if(candidatePhrases.get(index).count() > candidatePhrase.count())
					{
						candidatePhrases.set(index, candidatePhrase);
					}
				}
			}
			return candidatePhrases;
		}
	}
	
	/**
	 * &nbsp;&nbsp;&nbsp;&nbsp;分析段中以候选词为中心产生的候选短语，候选短语要求前后两个词必须是动词或者是名词，而且长度要大于或等于2。
	 * <p>&nbsp;&nbsp;&nbsp;&nbsp;对这个函数进行了优化，比如段的情况是A...B...C...D，B和C都是候选词，A和D是边界，如果以C为中心词的候选短语计算完毕，
	 * 那么计算以B为中心词的候选短语的时候，B扩展到C的时候，就可以马上停止，因为往后面扩展的短语，他们的得分肯定都计算完了;
	 * <br>&nbsp;&nbsp;&nbsp;&nbsp;同样，如果以B为中心词的候选短语计算完毕，那么计算以C为中心词的时候，当C扩展到B的时候，那C开始扩展的在B前面的那些词
	 * 组成的短语，肯定也计算完毕了。
	 * <p> 计算的起始位置为  [start...mid...end)
	 * @param segment	段
	 * @param start		起始位置（包括该位置）
	 * @param mid		中心词位置
	 * @param end		终止位置（不包括该位置）
	 * @param alreadyWords 已经计算完的候选词集合
	 * @return 返回扩展的候选短语
	 */
	private List<CandidatePhrase> genCandidatePhrases(SeqSegment segment,int start,int mid,int end, List<Word> alreadyWords,CandidateWord canword)
	{
		List<CandidatePhrase> phrases = new ArrayList<CandidatePhrase>();
		int nvCount = 0;
		for(int i = mid;i>=start;i--)
		{
			nvCount = 1;	//中心词算一个
			SeqWord leftWord = segment.getWord(i);
			//如果左边的这个词已经被计算完了，那就跳出循环
			if(alreadyWords.indexOf(leftWord) != -1)
			{
				break;
			}
			if((leftWord.getType() == Type.NOUN || leftWord.getType() == Type.VERB) && leftWord.length() >= 2)
			{
				nvCount++;
				for(int j=mid;j<end;j++)
				{
					SeqWord rightWord = segment.getWord(j);
					//如果右边的这个词已经被计算完了，那就后面的词就不要计算了，直接跳出循环
					if(alreadyWords.indexOf(rightWord) != -1)
					{
						break;
					}
					if((rightWord.getType() == Type.NOUN || rightWord.getType() == Type.VERB))
					{
						nvCount++;
						if(rightWord.length() < 2)
							continue;
						//修正nvCount
						if(i == mid)nvCount--;
						if(j == mid)nvCount--;
						//以leftWord和rightWord为边界，以mid对应的词为中心词，组成一个候选短语
						List<SeqWord> seqWords = new ArrayList<SeqWord>();
						List<Word> wordSet = new ArrayList<Word>();
						for(int t=i;t<=j;t++)
						{
							SeqWord currWord = segment.getWord(t);
							SeqWord seqWord = new SeqWord(currWord.getText(), currWord.getType(), currWord.getRelationToQuery(), t);//这里的偏移还是用以前段的偏移
							Word word = new Word(currWord);
							seqWords.add(seqWord);
							//wordSet只保存动、名词，这样合适吗？？？？
							if(((word.getType() == Type.NOUN || word.getType() == Type.VERB) && word.length() >= 2) && wordSet.indexOf(word) == -1)
								wordSet.add(word);
						}
						CandidatePhrase tmpPhrase = new CandidatePhrase(segment.getWord(mid), seqWords, wordSet,nvCount,canword);
						//添加短语具体的段信息，这个时候没有添加文档信息
						tmpPhrase.addPhraseSegment(new PhraseSegment(segment, i, j));
						phrases.add(tmpPhrase);
					}
				}
			}
		}
		return phrases;
	}
	
	/**
	 * 计算以词centerWord为中心扩展出的短语的左右独立性得分，选取独立性得分最大的短语作为该词的短语
	 * <br>由同一个候选词扩展的多个独立性得分相同的候选短语，选择那个不被包含的文档数最少的那个短语作为该词的候选短语
	 * @param centerWord 中心词
	 * @param phrases	 该中心词扩展出的短语集合
	 * @return
	 */
	private CandidatePhrase getBestPhrases(CandidateWord centerWord,List<CandidatePhrase> phrases)
	{
		//计算短语的独立性得分，选取得分的最高的短语为该查询词扩展得到的短语
		int length = phrases.size();
		double max = -10000;
		List<Integer> maxPhrases = new ArrayList<Integer>();							//最大独立性得分的的短语的下标编号集合
		List<Pair<Double, Double>> maxScores = new ArrayList<Pair<Double,Double>>();	//最大的独立性得分短语的左右独立性得分情况
																						//注意第i个score对应第maxPhrases.get(i)的得分
		for(int t=0;t<length;t++)
		{
			CandidatePhrase phrase = phrases.get(t);
			Pair<Double, Double> pair = calLRScore(phrase);
			double leftScore = pair.getFirst();
			double rightScore = pair.getSecond();
			if(leftScore >= INDEPENDENCE_THRESHOLD && rightScore >= INDEPENDENCE_THRESHOLD )
			{
				double score = (leftScore+rightScore)/2;
				if(score > max)//如果独立性得分大于当前最大得分，
				{
					max = score;
					//清空最大得分短语下标集合，并加上t
					maxPhrases.clear();
					maxScores.clear();
					maxPhrases.add(t);		//保存下标
					maxScores.add(pair);	//保存得分
				}else if(score == max){
					//如果独立性得分和当前最大得分相同，这个地方可以做标签层次化扩展，因为同一个中心词，表述的意思应该是关联的，可以分多个分支
					//目前选择长度大的，但也不能太长，不能超过4个
					//最大得分短语下标集合加上t
					maxPhrases.add(t);		//保存下标
					maxScores.add(pair);	//保存得分
				}
			}
		}
		//由同一个候选词扩展的多个独立性得分相同的候选短语，选择那个不被包含的文档数最少的那个短语作为该词的候选短语
		if(maxPhrases.size() == 0)
			return null;
		if(maxPhrases.size() == 1){//如果最大的得分短语只有一个
			CandidatePhrase phrase = phrases.get(maxPhrases.get(0));
			phrase.setLeftScore(maxScores.get(0).getFirst());
			phrase.setRightScore(maxScores.get(0).getSecond());
			return phrase;
		}else {//如果有多个候选短语独立性得分等于最大的独立性得分，选择那个不被包含的文档数最少的那个短语作为该词的候选短语
			int size = maxPhrases.size();
			int minInex = 0;
			double minNotCoveredRate = calNotCoveredRate(phrases.get(maxPhrases.get(0)));;
			for(int i=1;i<size;i++)
			{
				double notCoveredRate = calNotCoveredRate(phrases.get(maxPhrases.get(i)));
				if(notCoveredRate < minNotCoveredRate)
				{
					minInex = i;
					minNotCoveredRate = notCoveredRate;
				}
			}
			CandidatePhrase phrase = phrases.get(maxPhrases.get(minInex));
			phrase.setLeftScore(maxScores.get(minInex).getFirst());
			phrase.setRightScore(maxScores.get(minInex).getSecond());
			return phrase;
		}
	}
	
	/**
	 * 计算一个短语中那些无意义的字在和这个短语关联的文档中，不被包含的文档比率
	 * @param phrase
	 * @return
	 */
	private double calNotCoveredRate(CandidatePhrase phrase)
	{
		//List<Integer> relationDocs = phrase.getDocs();						//获取和该短语关联的文档下标集合
		List<PhraseSegment> relationSegments = phrase.getPhraseSegments();	//该短语关联文档对应的分段信息
		int DOC_NUM = relationSegments.size();
		//if(DOC_NUM != relationDocs.size())
			//System.err.println("出错了，文档和段对不上");
		if(DOC_NUM == 1)//如果只有一个文档相关联，直接返回0
			return 0;
		List<SeqWord> seqWords = phrase.getSeqWords();
		int WORD_NUM = seqWords.size();
		int invalidLength = 0;
		int notCoveredDoc = 0;
		for(int j=0;j<WORD_NUM;j++)
		{
			SeqWord word = seqWords.get(j);
			if((word.getType() == Type.NOUN || word.getType() == Type.VERB) && word.length() >= 2)
				continue;
			if(word.getType() == Type.JIECI || word.getType() == Type.ZHUCI || word.getType() == Type.CONN)
				continue;
			invalidLength += word.length();
			int tmpNotCoveredDocNum = 0;
			for(int i=0;i<DOC_NUM;i++)
			{
				PhraseSegment segment = relationSegments.get(i);
				if(!segment.containWord(word.getText()))
				{
					tmpNotCoveredDocNum++;
				}
			}
			notCoveredDoc += tmpNotCoveredDocNum*word.length();
		}
		if(invalidLength == 0)
		{
			return 0;
		}else {
			int result = notCoveredDoc/invalidLength;//这个短语那些无意义的字平均不被包含的文档数
			return ((double)result)/DOC_NUM;
		}
	}
	
	/**
	 * 根据候选短语，对所有文档进行聚类分析，返回聚类结果
	 * @param phrases
	 * @return
	 */
	private ClusterResult[] cluster(List<CandidatePhrase> phrases)
	{
		int DOC_NUM = this.docWords.length;
		int PHRASE_NUM = phrases.size();
		ClusterResult[] results = new ClusterResult[PHRASE_NUM+1];
		//给各聚类结果申请内存，并设置其他标签
		for(int i=0;i<PHRASE_NUM;i++)
			results[i] = new ClusterResult(phrases.get(i).getLabel());
		results[PHRASE_NUM] = new ClusterResult(new Label("其他", 0));
		
		
		/*for(int j=0;j<PHRASE_NUM;j++)
		{
			int maxIndex = 0;
			for(int docIndex =0;docIndex<DOC_NUM;docIndex++)
			{
				if(calRelation(docIndex, phrases.get(j)) >= PHRASE_DOC_RELATION_THRESHOLD)
					results[j].addDoc(this.docs[docIndex]);
				else results[PHRASE_NUM].addDoc(this.docs[docIndex]);
			}
		}*/
		//循环遍历文档，寻找语义最近的类别并划分
		for(int docIndex =0;docIndex<DOC_NUM;docIndex++)
		{
			int bestRefPhrase = getRefPhrase(docIndex, phrases);
			if(bestRefPhrase != -1)
			{
				results[bestRefPhrase].addDoc(this.docs[docIndex]);
			}else {//如果没有，就计算和文档语义关系最近的短语编号
				int maxScore = -1;
				int maxIndex = -1;
				for(int j=0;j<PHRASE_NUM;j++)
				{
					int tmp = getRelationScore(docIndex, phrases.get(j));
					if(tmp != -1 && maxScore < tmp)
					{
						maxIndex = j;
						maxScore = tmp;
					}
				}
				if(maxIndex != -1)
					results[maxIndex].addDoc(this.docs[docIndex]);
				else results[PHRASE_NUM].addDoc(this.docs[docIndex]);
			}
			
		}
		return results;
	}
	
	/**
	 * 寻找和文档docIndex存在关联关系的短语编号
	 * @param docIndex
	 * @param phrases
	 * @return 如果存在就返回编号，否则返回-1
	 */
	private int getRefPhrase(int docIndex,List<CandidatePhrase> phrases)
	{
		int size = phrases.size();
		int result = -1;
		for(int i=0;i<size;i++)
		{
			if(phrases.get(i).getDocs().contains(docIndex))
			{
				result = i;
				break;
			}
		}
		return result;
	}
	
	/**
	 * 计算文档和候选短语的关联程度
	 * @param docIndex
	 * @param phrase
	 * @return 如果大于给定阈值，就返回关联程度得分，否则返回-1
	 */
	private int getRelationScore(int docIndex,CandidatePhrase phrase) {
		List<Integer> refDocs = phrase.getDocs();
		int result = 0;
		for (int tmp : refDocs) {
			result += this.docSimMatrix[docIndex][tmp];
		}
		int threshold = (int)(PHRASE_DOC_RELATION_THRESHOLD*refDocs.size()*10);
		if(result >= threshold)//做一个过滤
			return result;
		else return -1;
	}
	
	/**
	 * 计算文档和候选短语之间的关联度
	 * <br>对文档的每个分段，计算分段和候选词的关联度，返回最大的关联度
	 * @param docIndex	文档编号
	 * @param phrase	候选短语
	 * @return
	 */
	private double calRelation(int docIndex,CandidatePhrase phrase)
	{
		//如果该文档和候选短语相关联，直接返回1
		if(phrase.getDocs().indexOf(docIndex) != -1)
			return 1;
		SeqDoc seqDoc = this.seqDocs[docIndex];
		int segmentNum = seqDoc.getSegmentNum();
		double maxScore = -1;
		for(int i=0;i<segmentNum;i++)
		{
			double score = calRelation(seqDoc.getSegment(i), phrase);
			if(maxScore < score)
				maxScore = score;
		}
		return maxScore;
	}
	
	/**
	 * 计算分段和候选短语之间的关联程度
	 * @param segment	分段
	 * @param phrase	候选短语
	 * @return
	 */
	private double calRelation(SeqSegment segment,CandidatePhrase phrase)
	{
		List<SeqWord> words = segment.getWords();			//获取分段中包含的词
		List<Word> wordSetInPhrases = phrase.getWordSet();	//获取短语中包含的词集
		int count = 0;										//记录有多少个词是在候选短语中包含的
		int size = words.size();							//分段中词的个数
		for(int i=0;i<size;i++)
		{
			if(wordSetInPhrases.contains(words.get(i)))
				count++;
		}
		if(size == 0)
			return 0;
		return (double)count/size;
	}
	
	/**
	 * 计算短语的左右独立性得分
	 * @param phrase	待计算的短语
	 * @return
	 */
	private Pair<Double, Double> calLRScore(CandidatePhrase phrase)
	{
		return new Pair<Double, Double>(calLeftScore(phrase),calRightScore(phrase));
	}
	
	/**
	 * 计算候选短语左独立性分数
	 * @param phrase 候选短语
	 * @return
	 */
	private double calLeftScore(CandidatePhrase phrase)
	{
		List<Integer> phraseRefs = phrase.getDocs();										//和该短语有关联的文档
		Word leftWord = phrase.getLeftWord();												//短语最左边的那个词
		int indexInMatrix = this.allWords.indexOf(leftWord.getText());						//最左边的那个词在全局词中的坐标，这个一定可以找到，
																							//因为短语的边界，一定是动词或名词，而且长度大于等于2
		if(this.leftRightScores[indexInMatrix].getFirst() != INVALID_SCORE)					//如果这个词已经算过了，就不要算了
			return this.leftRightScores[indexInMatrix].getFirst();
		
		Map<Integer, List<Integer>> refs = this.allWords.getWord(indexInMatrix).getRefs();	//找出这个词反引用位置<文档编号,段号集合>
		
		
		//对所有文档，如果包含了短语最左边的那个词（leftWord），统计它们以leftWord为边界的情况，
		//分两方面进行统计，一方面是全部文档，一方面是和这个短语有关联的文档
		Map<Word, Integer> allPreWord = new HashMap<Word, Integer>();	//记录leftWord前面那个词的出现的情况<词，词的出现次数>
		Map<Word, Integer> refPreWord = new HashMap<Word, Integer>();	//对和短语相关的文档，记录leftWord前面那个词的出现的情况<词，词的出现次数>
		int allEdgeCount = 0;											//计算以leftWord为分段开头的次数
		int refEdgeCount = 0;											//对和短语相关的文档，计算以leftWord为分段开头的次数
		
		//对包含该短语最左边的那个词的所有文档进行遍历，统计它作为边界的情况
		Iterator<Map.Entry<Integer, List<Integer>>> iterator = refs.entrySet().iterator();
		while (iterator.hasNext()) {
			Map.Entry<Integer, List<Integer>> entry = iterator.next();
			int docIndex = entry.getKey();
			SeqDoc currDoc = this.seqDocs[docIndex];				//当前文档
			boolean isDocRef = phraseRefs.contains(docIndex);		//这个文档是否和该短语有关联关系
			List<Integer> segments = entry.getValue();
			//获取最左边这个词在文档docIndex中的反引用信息<段号，段内偏移集合>
			Map<Integer, List<Integer>> refInDoc = this.docWords[docIndex].getWord(leftWord.getText()).getRefs();	
			int size = segments.size();
			for(int i=0;i<size;i++)
			{
				int currSegment = segments.get(i);
				List<Integer> offsets = refInDoc.get(currSegment);			//获取第i段的反引用信息(段内偏移集合)
				int length = offsets.size();
				//计算左边界
				if(offsets.get(0) == 0)
				{
					allEdgeCount++;
					if(isDocRef)
						refEdgeCount++;
				}
				//计算后面的情况
				for(int j=1;j<length;j++)
				{
					SeqWord preWord = currDoc.getWord(currSegment, offsets.get(j)-1);//获取前一个词
					Integer tmpAllPreCount = allPreWord.get((Word)preWord);
					if(tmpAllPreCount == null)
						allPreWord.put(preWord, 1);
					else allPreWord.put(preWord, tmpAllPreCount+1);
					if(isDocRef)
					{
						Integer tmpRefPreCount = refPreWord.get((Word)preWord);
						if(tmpRefPreCount == null)
							refPreWord.put(preWord, 1);
						else refPreWord.put(preWord, tmpRefPreCount+1);
					}
				}
			}
		}
		//统计全局的情况
		int maxTimes = 0;	//出现在这个短语最左边的词的前一个词的最多次数
		int allPreSum = 0;
		Iterator<Map.Entry<Word, Integer>> allPreIterator = allPreWord.entrySet().iterator();
		while (allPreIterator.hasNext()) {
			Map.Entry<Word, Integer> entry = allPreIterator.next();
			int count = entry.getValue();
			if(maxTimes < count)
				maxTimes = count;
			allPreSum += count;
		}
		double allEdgeRate = 0;												//最左边那个词作为边界的比例
		if((allEdgeCount+allPreSum) != 0)
			allEdgeRate = (double)allEdgeCount/(allEdgeCount+allPreSum);	
		double preStabeRate = 0;											//出现在前面次数最多的那个词的稳定率
		if(allPreSum != 0)
			preStabeRate = (double)maxTimes/allPreSum;;				
		//统计和该短语有相关性的文档的情况
		int refPreSum = 0;
		Iterator<Map.Entry<Word, Integer>> refPreIterator = refPreWord.entrySet().iterator();
		while (refPreIterator.hasNext()) {
			Map.Entry<Word, Integer> entry = refPreIterator.next();
			refPreSum += entry.getValue();
		}
		double refEdgeRate = 0;												//相关文档中，最左边那个词作为边界的比例
		if((refEdgeCount+refPreSum) != 0)
			refEdgeRate = (double)refEdgeCount/(refEdgeCount+refPreSum);	
		//计算左独立性分数
		double leftScore = 7.0*(0.3*allEdgeRate + 0.7*refEdgeRate ) - 3.0*preStabeRate;
		//更新左独立性得分（这个词肯定是查询词、动词、或者是名词）
		this.leftRightScores[indexInMatrix].setFirst(leftScore);
		
		return leftScore;
	}
	
	/**
	 * 计算候选短语的右独立性分数
	 * @param phrase
	 * @return
	 */
	private double calRightScore(CandidatePhrase phrase)
	{
		List<Integer> phraseRefs = phrase.getDocs();										//和该短语有关联的文档
		Word rightWord = phrase.getRightWord();												//短语最右边的那个词
		int indexInMatrix = this.allWords.indexOf(rightWord.getText());						//最右边的那个词在全局词中的坐标，这个一定可以找到，
																							//因为短语的边界，一定是动词或名词，而且长度大于等于2
		if(this.leftRightScores[indexInMatrix].getSecond() != INVALID_SCORE)				//如果这个词已经算过了，就不要算了
			return this.leftRightScores[indexInMatrix].getSecond();
		
		Map<Integer, List<Integer>> refs = this.allWords.getWord(indexInMatrix).getRefs();	//找出这个词反引用位置<文档编号,段号集合>
		
		
		//对所有文档，如果包含了短语最右边的那个词（rightWord），统计它们以rightWord为边界的情况，
		//分两方面进行统计，一方面是全部文档，一方面是和这个短语有关联的文档
		Map<Word, Integer> allAfterWord = new HashMap<Word, Integer>();	//记录rightWord后面那个词的出现的情况<词，词的出现次数>
		Map<Word, Integer> refAfterWord = new HashMap<Word, Integer>();	//对和短语相关的文档，记录rightWord后面那个词的出现的情况<词，词的出现次数>
		int allEdgeCount = 0;											//计算以rightWord为分段结尾的次数
		int refEdgeCount = 0;											//对和短语相关的文档，计算以rightWord为分段结尾的次数
		
		//对包含该短语最右边的那个词的所有文档进行遍历，统计它作为边界的情况
		Iterator<Map.Entry<Integer, List<Integer>>> iterator = refs.entrySet().iterator();
		while (iterator.hasNext()) {
			Map.Entry<Integer, List<Integer>> entry = iterator.next();
			int docIndex = entry.getKey();
			SeqDoc currDoc = this.seqDocs[docIndex];				//当前文档
			boolean isDocRef = phraseRefs.contains(docIndex);		//这个文档是否和该短语有关联关系
			List<Integer> segments = entry.getValue();
			//获取最右边这个词在文档docIndex中的反引用信息<段号，段内偏移集合>
			Map<Integer, List<Integer>> refInDoc = this.docWords[docIndex].getWord(rightWord.getText()).getRefs();	
			int size = segments.size();
			for(int i=0;i<size;i++)
			{
				int currSegment = segments.get(i);
				List<Integer> offsets = refInDoc.get(currSegment);			//获取第i段的反引用信息(段内偏移集合)
				int length = offsets.size();
				//计算右边界
				if(offsets.get(length-1) == (currDoc.getSegment(currSegment).length()-1))
				{
					allEdgeCount++;
					if(isDocRef)
						refEdgeCount++;
				}
				//计算前面的情况
				for(int j=0;j<(length-1);j++)
				{
					SeqWord afterWord = currDoc.getWord(currSegment, offsets.get(j)+1);//获取后一个词
					Integer tmpAllAfterCount = allAfterWord.get((Word)afterWord);
					if(tmpAllAfterCount == null)
						allAfterWord.put(afterWord, 1);
					else allAfterWord.put(afterWord, tmpAllAfterCount+1);
					if(isDocRef)
					{
						Integer tmpRefAfterCount = refAfterWord.get((Word)afterWord);
						if(tmpRefAfterCount == null)
							refAfterWord.put(afterWord, 1);
						else refAfterWord.put(afterWord, tmpRefAfterCount+1);
					}
				}
			}
		}
		//统计全局的情况
		int maxTimes = 0;	//出现在这个短语最右边的词的后一个词的最多次数
		int allAfterSum = 0;
		Iterator<Map.Entry<Word, Integer>> allAfterIterator = allAfterWord.entrySet().iterator();
		while (allAfterIterator.hasNext()) {
			Map.Entry<Word, Integer> entry = allAfterIterator.next();
			int count = entry.getValue();
			if(maxTimes < count)
				maxTimes = count;
			allAfterSum += count;
		}
		double allEdgeRate = 0;													//最右边那个词作为边界的比例
		if((allEdgeCount+allAfterSum) != 0)
			allEdgeRate = (double)allEdgeCount/(allEdgeCount+allAfterSum);	
		double afterStabeRate = 0;												//出现在后面次数最多的那个词的稳定率
		if(allAfterSum != 0)
			afterStabeRate = (double)maxTimes/allAfterSum;					
		//统计和该短语有相关性的文档的情况
		int refAfterSum = 0;
		Iterator<Map.Entry<Word, Integer>> refAfterIterator = refAfterWord.entrySet().iterator();
		while (refAfterIterator.hasNext()) {
			Map.Entry<Word, Integer> entry = refAfterIterator.next();
			refAfterSum += entry.getValue();
		}
		double refEdgeRate = 0;													//相关文档中，最右边那个词作为边界的比例
		if((refEdgeCount+refAfterSum) != 0)
			refEdgeRate = (double)refEdgeCount/(refEdgeCount+refAfterSum);
		//计算右独立性分数
		double rightScore = 7.0*(0.3*allEdgeRate + 0.7*refEdgeRate) - 3.0*afterStabeRate;
		
		//更新左独立性得分（这个词肯定是查询词、动词、或者是名词）
		this.leftRightScores[indexInMatrix].setSecond(rightScore);
		
		return rightScore;
	}
	
	/**
	 * 对候选短语进行打分，并根据打分对短语由高到低进行排序
	 * <br>短语评分由四个部分组成：
	 * <br>1：短语独立性得分
	 * <br>2：短语和查询词距离得分
	 * <br>3：短语关联的文档的相似度得分
	 * <br>4：短语占标题的比率得分
	 * @param phrases
	 */
	private List<CandidatePhrase> scoreLable(List<CandidatePhrase> phrases)
	{
		int size = phrases.size();
		for(int i=0;i<size;i++)
		{
			double score = scoreLable(phrases.get(i));
			phrases.get(i).setScore(score);
		}
		Collections.sort(phrases);
		return phrases;
	}
	
	/**
	 * 对候选短语进行打分，并根据打分对短语由高到低进行排序
	 * <br>短语评分由四个部分组成：
	 * <br>1：短语独立性得分
	 * <br>2：短语和查询词距离得分
	 * <br>3：短语关联的文档的相似度得分
	 * <br>4：短语占标题的比率得分
	 * @param phrase
	 * @return
	 */
	private double scoreLable(CandidatePhrase phrase)
	{
		double independenceScore = 0;	//短语独立性得分
		double disToQueryScore = 0;		//短语和查询词距离得分
		double docSimScore = 0;			//短语关联的文档的相似度得分
		double titleRateScore = 0;		//短语占标题的比率得分
		
		//计算短语独立性得分
		independenceScore = (phrase.getLeftScore()+phrase.getRightScore())/2;
		
		//计算和查询词距离得分
		disToQueryScore = -distanceToQuery(phrase);
		
		//计算关联的文档相似度得分
		List<Integer> relationDocs = phrase.getDocs();
		int size = relationDocs.size();
		List<Integer> tmpScores = new ArrayList<Integer>();
		for(int i=0;i<size;i++){
			int docIndex1 = relationDocs.get(i);
			for(int j=i+1;j<size;j++)
			{
				int docIndex2 = relationDocs.get(j);
				tmpScores.add(this.docSimMatrix[docIndex1][docIndex2]);
			}
		}
		docSimScore = average(10, tmpScores)/4;
		
		//计算短语占标题的比率得分
		List<TitleFlag> flags = phrase.getTitleFlags();
		int count = 0;
		for (TitleFlag titleFlag : flags) {
			if(titleFlag == TitleFlag.YES)
				count++;
		}
		titleRateScore = (double)count/flags.size();
		
		//总得分
		double score = independenceScore + disToQueryScore + docSimScore + titleRateScore;
		return score;
	}
	
	/**
	 * 计算候选短语和查询词之间的最小距离（类似编辑距离）
	 * @param phrase
	 * @return
	 */
	private double distanceToQuery(CandidatePhrase phrase)
	{
		List<PhraseSegment> segments = phrase.getPhraseSegments();
		int size = segments.size();
		List<Integer> distances = new ArrayList<Integer>();
		for(int i=0;i<size;i++)
		{
			PhraseSegment tmpSegment = segments.get(i);
			int length = tmpSegment.length();
			int start = tmpSegment.getStart();
			int end = tmpSegment.getEnd();
			int min = Integer.MAX_VALUE;
			for(int j=0;j<length;j++)
			{
				if(tmpSegment.getWord(j).getRelationToQuery() != RelationToQuery.NOTHING)
				{
					if(j<start)
					{
						min = Math.min(min, start-j);
					}else if(j>end)
					{
						min = Math.min(min, j-end);
					}
					else{
						min = 0;
						break;
					}
				}
			}
			if(min > 10 )//如果不包含查询词
			{
				min = 10;
			}
			distances.add(min);
		}
		return average(6, distances);
	}
	
	/**
	 * 求前面topN大个数的平均数
	 * @param topN
	 * @param list
	 * @return
	 */
	private double average(int topN,List<Integer> list)
	{
		Collections.sort(list,Collections.reverseOrder());
		if(topN <= 0 || list.size() == 0)
			return 0;
		topN = Math.min(topN, list.size());
		double result = 0;
		for(int i=0;i<topN;i++)
		{
			result += list.get(i);
		}
		return result/topN;
	}
}